Pasch Hypergraph

In geometry, a truncated projective plane (TPP), also known as a dual affine plane, is a special kind of a hypergraph or geometric configuration that is constructed in the following way.

* Take a finite projective plane.
* Remove one of the points (vertices) in the plane.
* Remove all lines (edges) containing that point.

These objects have been studied in many different settings, often independent of one another, and so, many terminologies have been developed. Also, different areas tend to ask different types of questions about these objects and are interested in different aspects of the same objects.

Example: the Pasch hypergraph

Consider the Fano plane, which is the projective plane of order 2. It has 7 vertices and 7 edges .

It can be truncated e.g. by removing the vertex 7 and the edges containing it. The remaining hypergraph is the TPP of order 2. It has 6 vertices and 4 edges . It is a tripartite hypergraph with sides ,, (which are exactly the neighbors of the removed vertex 7). It is also called the ''Pasch hypergraph'', due to its connection with Pasch's axiom.

It is a 2- regular hypergraph (each vertex is in exactly two edges), and its maximum matching is of size 1 (every two of its edges intersect).

Combinatorics of dual affine planes

A finite projective plane of order has + 1 points on every line ( in the hypergraph description). There are total points and an equal number of lines. Each point is on + 1 lines. Every two distinct points lie on a unique line and every two distinct lines meet at a unique point.

By removing a point and all the lines that pass through that point, the configuration that is left has points, ² lines, each point is on lines and each line contains + 1 points. Each pair of distinct lines still meet at a unique point, but two distinct points are on at most one line. This dual affine plane is thus a configuration of type ().

The points can be partitioned into + 1 sets of points apiece, where no two points in the same partition set are joined by a line. These sets are the analogs of classes of parallel lines in an affine plane, and some authors refer to the points in a partition piece as ''parallel points'' in keeping with the dual nature of the structure.

Projective planes constructed from finite fields ( Desarguesian planes) have automorphism groups that act transitively on the points of the plane, so for these planes the point removed to form the dual affine plane is immaterial, the results of choosing different points are isomorphic. However, there do exist non-Desarguesian planes and the choice of point to remove in them may result in non-isomorphic dual affine planes having the same parameters.

An affine plane is obtained by removing a line and all the points on that line from a projective plane. Since a projective plane is a self-dual configuration, the dual configuration of an affine plane is obtained from a projective plane by removing a point and all the lines through that point.
Hence the name of this configuration.

Hypergraph properties

It is known that the projective plane of order ''r''-1 exists whenever ''r''-1 is a prime power; hence the same is true for the TPP.

The finite projective plane of order ''r''-1 contains ''r''²-''r''+1 vertices and ''r''²-''r''+1 edges; hence the TPP of order ''r''-1 contains ''r''²-''r'' vertices and ''r''²-''2r''+1 edges.

The TPP of order ''r''-1 is an ''r''-partite hypergraph: its vertices can be partitioned into ''r'' parts such that each hyperedge contains exactly one vertex of each part. For example, in the TPP of order 2, the 3 parts are , and . In general, each of the ''r'' parts contains ''r''-1 vertices.

Each edge in a TPP intersects every other edge. Therefore, its maximum matching size is 1:

$\nu(H)=1$.

On the other hand, covering all edges of the TPP requires all ''r''-1 vertices of one of the parts. Therefore, its minimum vertex-cover size is ''r''-1:

$\tau(H)=r-1$.

Therefore, the TPP is an extremal hypergraph for Ryser's conjecture.

The minimum fractional vertex-cover size of the TPP is ''r''-1 too: assigning a weight of 1/''r'' to each vertex (which is a vertex-cover since each hyperedge contains ''r'' vertices) yields a fractional cover of size (''r''²-''r'')/''r''=''r''-1.

Its maximum fractional matching size of the is ''r''-1 too: assigning a weight of 1/(''r-1'') to each hyperedge (which is a matching since each vertex is contained in ''r''-1 edges) yields a fractional matching of size (''r''²-''2r''+1)/(''r''-1)=''r''-1. Therefore:

$\tau^*(H)=\nu^*(H)=r-1$.

Note that the above fractional matching is perfect, since its size equals the number of vertices in each part of the ''r''-partite hypergraph. However, there is no perfect matching, and moreover, the maximum matching size is only 1. This is in contrast to the situation in bipartite graphs, in which a perfect fractional matching implies the existence of a perfect matching.

Design-theoretic aspects

Dual affine planes can be viewed as a point residue of a projective plane, a 1-design, and, more classically, as a tactical configuration.

Since they are not pairwise balanced designs (PBDs), they have not been studied extensively from the design-theoretic viewpoint. However, tactical configurations are central topics in geometry, especially finite geometry.

History

According to , the term "tactical configuration" appears to be due to E. H. Moore in 1896. For the history of dual configurations, see Duality (projective geometry)#History.

Notes

References

*
* {{Citation , last1=Dembowski , first1=Peter , title=Finite geometries , publisher= Springer-Verlag , location=Berlin, New York , series= Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44 , mr=0233275 , year=1968 , isbn=3-540-61786-8 , url-access=registration , url=https://archive.org/details/finitegeometries0000demb

Hypergraphs
Projective geometry